class Solution
{
public:
    int lengthOfLIS(vector<int> &nums)
    {
        int n = nums.size();
        vector<int> dp(n, 1);
        int max_sum = 1; // 初始化为最差的结果，也就是每一个数自己是子序列，所以全部初始化为1
        for (int i = 1; i < n; ++i)
        {
            for (int j = i - 1; j >= 0; --j)
            {
                if (nums[j] < nums[i])
                    dp[i] = max(dp[i], dp[j] + 1);
            }
            max_sum = max(max_sum, dp[i]);
        }
        return max_sum;
    }
};

class Solution
{
public:
    int wiggleMaxLength(vector<int> &nums)
    {
        int n = nums.size();
        vector<int> f(n, 1), g(n, 1);
        int max_num = 1;
        for (int i = 1; i < n; ++i)
        {
            for (int j = 0; j < i; ++j)
            {
                if (nums[j] < nums[i])
                {
                    f[i] = max(f[i], g[j] + 1);
                }
                else if (nums[j] > nums[i])
                {
                    g[i] = max(g[i], f[j] + 1);
                }
            }
            max_num = max(max_num, max(f[i], g[i]));
        }
        return max_num;
    }
};

class Solution
{
public:
    int findNumberOfLIS(vector<int> &nums)
    {
        int n = nums.size();
        vector<int> len(n, 1);   // len统计i结尾的最长递增子序列长度
        vector<int> count(n, 1); // count统计i结尾的最长递增子序列个数
        int max_len = 1;         // 查找最长递增子序列长度
        int max_count = 1;       // 查找最长递增子序列个数，并返回
        for (int i = 1; i < n; ++i)
        {
            // 我nums[i]可以跟在前面【0到i-1】任何一个或者多个位置后面
            for (int j = 0; j < i; ++j)
            {
                if (nums[j] < nums[i])
                {
                    // 子序列长度相等
                    if (len[j] + 1 == len[i])
                    {
                        count[i] += count[j];
                    }
                    // 新子序列必就子序列长度要大
                    else if (len[j] + 1 > len[i])
                    {
                        len[i] = len[j] + 1;
                        count[i] = count[j];
                    }
                }
            }
            // 在循环内判断
            // 我max_len是不是最长递增子序列，是的话个数+=count[i]里面存的该最长递增子序列的个数，就是最终结果
            if (max_len == len[i])
            {
                max_count += count[i];
            }
            // max_len如果不是最长递增子序列，那么更新我的max_len，并且让我的max_count等于最长递增子序列的个数也就是count[i]
            else if (max_len < len[i])
            {
                max_len = len[i];
                max_count = count[i];
            }
        }
        return max_count;
    }
};
class Solution
{
public:
    int findLongestChain(vector<vector<int>> &pairs)
    {
        sort(pairs.begin(), pairs.end()); // 排序，让我[i][0]一定大于[i-1][1]
        int n = pairs.size();
        vector<int> dp(n, 1);
        int max_num = 1;
        for (int i = 1; i < n; ++i)
        {
            for (int j = 0; j < i; ++j)
            {
                if (pairs[j][1] < pairs[i][0])
                {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            max_num = max(max_num, dp[i]);
        }
        return max_num;
    }
};

class Solution
{
public:
    int longestSubsequence(vector<int> &arr, int d)
    {
        // 优化1 ： 将arr元素中的，i与对应的最长定差子序列dp[i]，j与对应的最长定差子序列dp[j]放入哈希表中
        // 优化2 ： 我i和dp[i]，j和dp[j]都放入哈希表了，我还要dp表干嘛，直接使用哈希表就行了
        int n = arr.size();
        unordered_map<int, int> hash; // <arr[i],dp[i]>
        hash[arr[0]] = 1;             // 初始化
        int max_num = 1;
        for (int i = 1; i < n; ++i)
        {
            // 不用两个for循环了
            // arr[i]-d就是i结尾的等差子序列中，倒数第二个数据
            // 也就是【arr[i] - d ，比如：1,2,3,5,7,9 --->>> arr[i]=9那么arr[i]-d = 9-2 = 7】
            // 最后我i也是这个子序列的结尾，所以加上1

            // 如果i位置前面的没有最长子序列为0的话
            // 那么i位置自己就是最长子序列为1，此时 hash[arr[i]-d] + 1 --->>> 0+1 =1 结果正确
            hash[arr[i]] = hash[arr[i] - d] + 1;
            // if(arr[i]-arr[j]==d)
            // {
            // hash[i] = max(hash[i],hash[j] + 1);
            // }
            max_num = max(max_num, hash[arr[i]]);
        }
        return max_num;

        // int n = arr.size();
        // vector<int> dp(n,1);
        // for(int i=1;i<n;++i)
        // {
        //     for(int j =0;j<i;++j) // 不优化的话，arr数据过多会超时
        //     // for(int j =i-1;j>=0;--j)
        //     {
        //         if(arr[i]-arr[j]==d)
        //         {
        //             hash[i] = max(hash[i],hash[j] + 1);
        //         }
        //     }
        //     max_num = max(max_num,hash[i]);
        // }
        // return max_num;
    }
};

class Solution
{
public:
    int longestArithSeqLength(vector<int> &nums)
    {
        int n = nums.size();
        unordered_map<int, int> hash;
        int result = 2; // 以i和j为结尾，查找前面子序列的最大等差数列，所以i，j是两个值，那么最差情况为2，i，j构成等差数列
        vector<vector<int>> dp(n, vector<int>(n, 2));
        hash[nums[0]] = 0;
        ///--- 我们a的值可能在nums中很多位置都存在！【j < i】
        // 我们只需要保存最长等差数列的长度，也就是离着i，j最近的hash【a】的下标【最长的】
        // 如果我们i，j从前向后，那么为了得到hash【a】的下标离i，j最近的话，要遍历nums加判断，所以i和j的初始化位置要优化
        // 先固定倒数第二个数j，在枚举最后一个数i
        // 所有外层循环固定j，i从j+1位置到nums末尾进行枚举
        for (int j = 1; j < n; ++j)
        {
            //// hash[nums[j]] = j;// 不能放到上面，我们在处理j这个位置时，只包含j之前的位置的信息
            for (int i = j + 1; i < n; ++i)
            {
                int a = 2 * nums[j] - nums[i];
                if (hash.count(a))
                {
                    dp[j][i] = dp[hash[a]][j] + 1;
                }
                result = max(result, dp[j][i]);
            }
            hash[nums[j]] = j; // 一边插入nums数据到hash中与下标映射，一半进行动态规划
        }
        return result;
        // int n = nums.size();
        // unordered_map<int,int> hash;
        // int result = 2; // 以i和j为结尾，查找前面子序列的最大等差数列，所以i，j是两个值，那么最差情况为2，i，j构成等差数列
        // vector<vector<int>> dp(n,vector<int>(n,2));
        // hash[nums[0]] = 0;
        // // i和j的初始化位置要优化
        // for(int i=1;i<n;++i)
        // {
        //     hash[nums[i]] = i;// 一边插入nums数据到hash中与下标映射，一半进行动态规划
        //     for(int j=0;j<i;++j)
        //     {
        //         int a = 2 * nums[j] - nums[i];
        //         if(hash.count(a)  && hash[a]<j)
        //         {
        //             dp[j][i] = dp[hash[a]][j] + 1;
        //         }
        //         result = max(result,dp[j][i]);
        //     }
        // }
        // return result;
    }
};

class Solution
{
public:
    int lenLongestFibSubseq(vector<int> &arr)
    {
        int n = arr.size();
        // dp[i][j] : 以i和j两个为结尾的所有子序列中,最长的斐波那契子序列长度
        unordered_map<int, int> map;
        // a,b,c对应的就是arr里面条件成立的斐波那契子序列3个数
        // i,j对应的是b,c两个数在arr数组的下标和map里面的second
        // 不知道a在arr里面的下标，但是知道a在map里面对应的second，就够了
        for (int i = 0; i < n; ++i)
        {
            map[arr[i]] = i;
        }
        vector<vector<int>> dp(n, vector<int>(n, 2));
        int result = 2;
        // 题目要求子序列大于3，那么j是子序列最后一个位置数据，i就是子序列倒数第二个位置数据
        // 所以j从2开始，i从1开始，这样条件成立的话能够保证0位置也有数据，那么就有3个及以上数据，满足题目需求
        for (int j = 2; j < n; ++j)
        {
            for (int i = 1; i < j; ++i)
            {
                // a + arr[i] = arr[j] --- 斐波那契子序列
                int a = arr[j] - arr[i];
                if (map.count(a) == true && a < arr[i])
                {
                    dp[i][j] = dp[map[a]][i] + 1;
                }
                // 1、如果a存在，但是b<a<c 也就是3,1,4不满足题目严格递增；2、如果a不存在。两个条件对应的d[i][j]应该为2
                // 只有b和c没有a，就两个值。我们上面全部初始化空间为2了，所以这里不用管
                result = max(result, dp[i][j]);
            }
        }
        return result < 3 ? 0 : result; // 题目规定长度要大于3
    }
};

class Solution
{
public:
    int numberOfArithmeticSlices(vector<int> &nums)
    {
        int n = nums.size();
        // 1优化
        // 使用long long int防止2*nums[j]数据过大或者过小
        // 第二个参数要为vector<int>以便存储多个索引。最终遍历这些索引得到等差子序列个数
        unordered_map<long long int, vector<int>> hash;
        for (int i = 0; i < n; i++)
            hash[nums[i]].push_back(i);
        vector<vector<int>> dp(n, vector<int>(n));
        int sum = 0;
        for (int j = 2; j < n; j++) // 固定倒数第一个数
        {
            for (int i = 1; i < j; i++) // 枚举倒数第二个数
            {
                long long int a = (long long int)2 * nums[i] - nums[j];
                if (hash.count(a))
                {
                    for (auto e : hash[a])
                    {
                        if (e < i)
                        {
                            dp[i][j] += dp[e][i] + 1;
                        }
                    }
                }
                sum += dp[i][j];
            }
        }
        return sum;
    }
};